﻿// 4519. 正方形数组的数目.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <cmath>
using namespace std;
/*
https://www.acwing.com/problem/content/4522/
给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。

返回 A的正方形排列的数目。

两个排列 A1和 A2不同的充要条件是存在某个索引 i，使得 A1[i]≠A2[i]。

输入格式
第一行包含一个整数 n，表示数组 A 的长度。

第二行包含 n个整数 A[i]。

输出格式
一个整数，表示 A 的正方形排列的数目。

数据范围
1≤n≤12,

0≤A[i]≤109。

输入样例：
3
1 17 8
输出样例：
2
样例解释
[1,8,17] 和 [17,8,1] 都是有效的排列。


4
2 2 7 2
*/

unordered_map<int, set<int>> numpair;
unordered_map<int, int> numcnt;
const int N = 20;
int a[N];
int n;
int ans;

bool Check(int x) {
	int v = sqrt(x);
	if (x == v * v) {
		return true;
	}
	return false;
}


void dfs(int cnt, int lastsel) {
	if (cnt == n) {
		ans++;
		return;
	}

	for (auto curr : numpair[lastsel]) {
		if (numcnt[curr] != 0) {
			numcnt[curr]--;
			dfs(cnt + 1, curr);
			numcnt[curr]++;
		}
	}

}


int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t; cin >> t;
		a[i] = t;
		numcnt[t]++;
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (Check(a[i] + a[j])) {
				numpair[a[i]].insert(a[j]);
				numpair[a[j]].insert(a[i]);
			}
		}
	}


	for (auto e : numcnt) {
		int key = e.first;
		numcnt[key]--;
		dfs(1, key);
		numcnt[key]++;
	}

	cout << ans << endl;


	return 0;
}

